package com.lc.hot100.lc560;

import java.util.HashMap;
import java.util.Map;

public class Main {

}

class Solution1 {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i ++) {
        	s[i + 1] = nums[i] + s[i];
        }
        int res = 0;
        for (int i = 0; i <= n; i ++) {
        	for (int j = 0; j < i; j ++) {
        		if (k == s[i] - s[j]) {
        			res ++;
        		}
        	}
        }
        return res;
    }
}

 
class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        Map<Integer, Integer> mp = new HashMap<>();
        
        int sum = 0;
        mp.put(0, 1);
        for (int i = 0; i < n; i ++) {
        	sum += nums[i];
        	if (mp.containsKey(sum - k)) {
        		res += mp.get(sum - k);
        	} 
        	mp.put(sum, mp.getOrDefault(sum, 0) + 1);
        }
        
        return res;
    }
}
